#include<stdio.h>
#include<stdlib.h>
#include"tree.h"

TreeNode * Tree_delete(TreeNode * root,int value){

    if(NULL == root){

        return NULL;
    }
    if(root->value > value){

        root->left = Tree_delete(root->left,value);
        return root;
    }
    if(root->value < value){

        root->right = Tree_delete(root->right,value);
        return root;
    }
    // -找到节点了
    if(NULL == root->left && NULL== root->right){

        free(root);
        return NULL;
    }
    if(NULL == root->left){

        TreeNode * ptr = root;
        root = root->right;
        free(ptr);
        return root;
    }
    if(NULL == root->right){

        TreeNode * ptr = root;
        root = root->left;
        free(ptr);
        return root;
    }
    TreeNode * su = root->right;    // -这里可以选择左子树 也可以选择右子树 但是下面走的方式要变成right
    // -不能让su为空
    while(NULL!=su->left){

        su = su->left;
    }
    // -交换元素
    root->value = su->value;
    su->value = value;
    // -节点还没有删除 只是把这个要删除的节点与继承节点交换了一下值元素 而且把要删除的节点变换成了没有左子树的节点
    // -删除节点value
    root->right = Tree_delete(root->right,value);

    return root;
}
